This invention relates to computerized spreadsheet technology. A method of using a digital computer for the of recalculating the contents of spreadsheet's cells when they are affected by a modification of one or more cells in the spreadsheet is disclosed. The reader is directed to the DEFINITIONS section for the meaning of certain terms used herein.
A spreadsheet is an accounting tool which is typically used to model business, economic and other similar systems. A spreadsheet (also referred to generically as a "worksheet") is represented by a two-dimensional array with individual array elements, defined by row and column placement, referred to as "cells." Each cell in a spreadsheet can contain one of several information types, including text strings, mathematical formulas, numbers, and links or references to other cells. In a spreadsheet which models a small business, for example, a first cell might contain a number representing the business's revenue for a given year. A second cell might contain a formula for calculating the business's costs for the same year. A third cell in the spreadsheet might contain a formula which subtracts the value resulting from the formula in the second cell (costs) from the value of the first cell (revenue) with the result being the business's gross profit for the year. Additional cells containing data or formulas to calculate taxes and other business expenses may be added to expand the model. Together, the contents of the cells form a financial model of the business.
An important aspect of computerized spreadsheet technology is recalculation of the contents of the spreadsheet's cells after one or more cells have been modified. (As explained above, each cell in a spreadsheet is of a distinct information type, whether it be a number, formula, or otherwise. A cell which contains a formula or a number has a value associated with it which is simply the value of the number or the mathematical result of the formula. The term "recalculation" refers to the determination of a cell's new value after it or a cell upon which it depends for its value has been modified.)
Initially, the spreadsheet user enters various formulas and data in the spreadsheet cells to create a model. Thereafter, a spreadsheet user will often want to test several possible outcomes of a particular problem by modifying the parameters of his model, i.e., by modifying formulas or data in the spreadsheet cells. Modifications are also often made to correct errors in the model. Each cell modification potentially affects the value of several other cells in the spreadsheet. For example, a cell may contain a number representing a business's net profit. That cell may be referenced by many other cells in the spreadsheet which use it to calculate, for instance, taxes or dividends. Each of those cells may, in turn, be referenced by multiple other cells. Thus, a change in the contents of even a single spreadsheet cell can have wide-ranging effects on cells throughout the entire spreadsheet. Multiple cell modifications can, therefore, make recalculation of a sophisticated spreadsheet model a complex and time consuming process. Recalculation of a complete spreadsheet can involve not only moving data between numerous memory locations in the microprocessor, but also the performance of mathematical operations by the microprocessor on large quantities of data. These operations require large numbers of clock cycles and intensive use of the microprocessor, thereby slowing down other computer activities. Thus, a quick and efficient recalculation method presents a distinct advantage to the spreadsheet user.
The recalculation invention described herein performs recalculation in an optimal manner by maintaining an indication of which cells have been modified, examining each occupied cell in the spreadsheet only once in determining which cells have been affected by modification (and, thus, require recalculation), creating an ordered list of cells requiring recalculation, and visiting and recalculating only those cells which require recalculation.